#include "iostream"
#include "assert.h"
#include "queue"
#include "list"

using ElemType = char;

struct TreeNode
{
    ElemType data;
    TreeNode *left;
    TreeNode *right;

    // 构造
    ////////////////////////////////////////////////////////////////////
    static TreeNode *create()
    {
        auto r = (TreeNode *)malloc(sizeof(TreeNode));
        *r = TreeNode();
        return r;
    }
    static TreeNode *create(ElemType data)
    {

        auto r = (TreeNode *)malloc(sizeof(TreeNode));
        r->data = data;
        r->left = nullptr;
        r->right = nullptr;
        return r;
    }
    static TreeNode *create(ElemType data, TreeNode *l, TreeNode *r)
    {

        auto ret = (TreeNode *)malloc(sizeof(TreeNode));
        ret->data = data;
        ret->right = r;
        ret->left = l;
        return ret;
    }
    static TreeNode *create(TreeNode *l, TreeNode *r)
    {

        auto ret = (TreeNode *)malloc(sizeof(TreeNode));
        ret->right = r;
        ret->left = l;
        return ret;
    }
    //

    // 遍历
    ////////////////////////////////////////////////////////////////////
    void level_iter()
    {
        std::queue<TreeNode *> queue;
        auto node = this;
        queue.push(node);
        int level = 0;
        while (!queue.empty())
        {
            auto a = queue.front();
            queue.pop();
            TreeNode *first_push = nullptr;
            if (a->left)
            {
                queue.push(a->left);
                first_push = a->left;
            }
            if (a->right)
            {
                queue.push(a->right);
                if (!first_push)
                    first_push = a->right;
            }

            // //这一段比较重要，需要记一下
            // if (a == node) //取出来的a==这一层最后一个元素
            // {
            //     printf("%d\r\n", level);
            //     level++;
            //     if (!queue.empty())
            //     {
            //         node = queue.back();
            //         //因为是再这一层最后一个元素的前提下，
            //         // 所以队列的最后一个元素就是下一层最后一个元素
            //     }
            // }

            //换个思路
            if (a == node) //取出来的是这层第一个元素
            {
                printf("\r\n%d ", level);
                level++;
                node = first_push;
            }

            printf("%c,", a->data);
        }
        printf("\r\n");
    }
    //
};

TreeNode *handle(ElemType A[], ElemType B[], int &Abegin, int Bbegin, int Bend)
{
    if (Bbegin > Bend)
    {
        return nullptr;
    }
    auto node = TreeNode::create();
    if (Bbegin == Bend)
    {
        node->data = B[Bbegin];
        Abegin++;
        return node;
    }

    int i = Bbegin;
    for (; i <= Bend; i++)
    {
        if (A[Abegin] == B[i])
        {
            break;
        }
    }
    //用完 abegin，为下一次++
    Abegin++;
    node->data = B[i];
    node->left = handle(A, B, Abegin, Bbegin, i - 1);
    node->right = handle(A, B, Abegin, i + 1, Bend);
    return node;
}

void found_closest_father_of_AB(TreeNode *root, TreeNode *A, TreeNode *B)
{
    printf("looking for father of %c %c\r\n", A->data, B->data);

    auto p = root;
    std::list<TreeNode *> stack; //用list模拟战
    TreeNode *r;
    // bool A_found = false;
    // bool B_found = false;
    TreeNode *A_back = nullptr;
    TreeNode *B_back = nullptr; //记录找到B后。相对B往回退的指针
    while (p || !stack.empty())
    {
        if (p)
        {
            stack.push_back(p);
            p = p->left;
        }
        else
        {
            auto p1 = stack.back(); //访问栈顶，但是不出栈
            //A或b有一个没找到就继续遍历
            if (p1->right && r != p1->right) //未找到前提下继续正常遍历
            {                                //右子树非空，并且未被访问
                //转到右子树
                p = p1->right;
            }
            else
            { //右子树空或者右子树已被访问
                //出栈

                stack.pop_back();
                //p1可能是A_back父节点
                if (A_back)
                {
                    if (p1->left == A_back || p1->right == A_back)
                    {
                        A_back = p1;
                    }
                }
                if (B_back)
                {
                    if (p1->left == B_back || p1->right == B_back)
                    {
                        B_back = p1;
                    }
                }
                if (A_back && A_back == B_back)
                {
                    printf("found %c\r\n", A_back->data);
                    return;
                }
                //p1可能是第一个目标节点
                if (p1 == A) //若找到A
                {
                    A_back = A;
                }
                if (p1 == B) //若找到A
                {
                    B_back = B;
                }

                //非递归后续遍历最关键的两句
                r = p1;
                p = nullptr;
            }
        }
    }
}

void main()
{
    //   a
    //  / \
    // b   c
    // |\  | \
    // d e f  g
    //
    // 正序: a b d e c f g
    // 中序: a d b e f c g

    ElemType A[] = {'a', 'b', 'd', 'e', 'c', 'f', 'g'};
    ElemType B[] = {'d', 'b', 'e', 'a', 'f', 'c', 'g'};

    int abegin = 0;
    auto tree = handle(A, B, abegin, 0, 6);

    tree->level_iter();

    found_closest_father_of_AB(tree, tree->right->left, tree->left);
}